Turnbull China Bikeride/Turnbull China Bikeride - Disc 2.iso/BARNET/COMPILER/SATHER/!Sather/Library/Containrs/sa/h_set

Text File | 1996-04-09 | 5KB | 162 lines

---------------------------> Sather 1.1 source file <--------------------------
-- Author: Benedict A. Gomes <[e-mail]>
--    Much of the implementation was written by Holger
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: h_set.sa,v 1.6 1996/04/09 10:05:06 borisv Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
-------------------------------------------------------------------
class SET{E} < $SET{E} is  include H_SET{E}; end;
-------------------------------------------------------------------
class H_SET{E} < $SET{E} is
    -- Implementation of sets using dynamic hash tables.
    -- This implementation is also available of dealing with equal but
    -- not same objects.
   include SET_INCL{E} create->,size->;
   private include DYNAMIC_BUCKET_TABLE{E,BUCKET{E}}
     map_copy->copy, create->create;

   create_from(a: ARRAY{E}): SAME is
      return create(a);
   end;

   create(e: $ELT{E}): SAME is
      res ::= create;
      loop res.insert(e.elt!) end;
      return res;
   end;

   size: INT is return n_inds end;

   --              ------ Insertion/Removal ---------------
   insert(e:E) pre ~void(self) is
      h ::= hash(e);
      loop
     if elt_key_eq(bucket(h).list!.item,e) then return end;
      end;
      set_bucket( h, #BUCKET{E}(e,bucket(h)) );
      n_inds := n_inds + 1;
      update_insert
   end;

   delete(e: E) is discard ::= delete(e) end;

   clear is
      -- Extremely inefficient.  Must be rewritten by someone who has
      -- looked at the implementation (delete(elt!) may have problems)
      -- Creates a separate list of elements to delete to separte out
      -- iteration from modification
      elts: ARRAY{E} := #(n_inds);
      loop elts.set!(elt!) end;
      loop delete(elts.elt!) end;
   end;

   -- The next routines deal with the problem of elements
   -- being equal but not same.
   delete(e:E): E     pre ~void(self) is
      -- Removes an element from the set. Returns the deleted element.
      -- Returns void (or E::nil if E inherits $NIL{E}) if there is
      -- no element to delete.
      h ::= hash(e);
      b ::= bucket(h);
      prev ::= b; prev := void; -- NASTY HACK
      loop until!( void(b) or elt_key_eq(b.item,e) );
     prev := b;
     b := b.next
      end;
      if void(b) then return void end;
      res ::= b.item;
      if void(prev) then set_bucket( h, b.next )
      else  prev.next(b.next) end;
      n_inds := n_inds - 1;
      update_delete;
      return res
   end;

   insert_replace(e:E) pre ~void(self) is
      -- Inserts e into the set. If there is already an
      -- element equal to e in the set, the old element
      -- will be replaced.
      dummy ::= insert_replace(e)
    end;

    insert_replace(e:E): E   pre ~void(self)  is
      -- Does the same like insert_replace but returns
      -- the old element which is being replaced or the
      -- same object if there was no old one.
      old: E;
      h ::= hash(e);
      firstb ::= bucket(h);
      loop
     b ::= firstb.list!;
     old := b.item;
     if elt_key_eq(old,e) then
        b.item(e);
        return old
     end
      end;
      set_bucket(h,#BUCKET{E}(e,firstb));
      n_inds := n_inds + 1;
      update_insert;
      return e
   end;

   --              ------ Access/Measurement --------------
   has(e:E): BOOL pre ~void(self) is
      loop
     if elt_key_eq(bucket(hash(e)).list!.item,e) then return true end;
      end;
      return false;
   end;

   get(e:E): E  pre ~void(self) is
      -- Returns the element equal to 'e' from the set.
      -- Returns void or E::nil if there is no such element.
      -- Self may not be void.
      loop
     i ::= bucket(hash(e)).list!.item;
     if elt_key_eq(i,e) then return i end
      end;
      return elt_key_nil
   end;

   union(s: $RO_SET{E}): SAME is
      res ::= copy;
      loop res.insert(s.elt!) end;
      return res;
   end;

   intersection(s:$RO_SET{E}): SAME is
      res ::= #SAME;
      loop e ::= elt!; if s.has(e) then res.insert(e) end; end;
      return res;
   end;

   diff(s: $RO_SET{E}): SAME is
      res ::= #SAME;
      loop e ::= elt!; if ~s.has(e) then res.insert(e) end; end;
      return res;
   end;

   sym_diff(s: $RO_SET{E}): SAME is
      res ::= #SAME;
      loop e ::= elt!; if ~s.has(e) then res.insert(e) end; end;
      loop e ::= s.elt!; if ~has(e) then res.insert(e) end; end;
      return res;
   end;

   --              ------ Cursor --------------------------
   elt!: E pre ~void(self) is
      loop
     b ::= bucket( 0.upto!(bound+split_pos-1) );
     loop yield b.list!.item; end
      end
   end;

end; -- H_SET{E}
-------------------------------------------------------------------